package com.leetcode.partition4;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author `RKC`
 * @date 2021/11/8 17:41
 */
public class LC313超级丑数 {

    public static int nthSuperUglyNumber(int n, int[] primes) {
        //indices[i]表示因子primes[i]在dp中的下标
        int[] indices = new int[primes.length];
        //dp[i]：第i+1个超级丑数
        long[] dp = new long[n];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            //枚举所有的因子乘积，选择最小值
            for (int j = 0; j < primes.length; j++) {
                dp[i] = Math.min(dp[i], dp[indices[j]] * primes[j]);
            }
            //只要是被选中的最小值，索引都往前移
            for (int j = 0; j < primes.length; j++) {
                if (dp[i] % primes[j] == 0) {
                    indices[j]++;
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return (int) dp[n - 1];
    }

    public static void main(String[] args) {
        int[] primes = {2, 7, 13, 19};
        int n = 12;
        System.out.println(nthSuperUglyNumber(n, primes));
    }

    private static int treeSet(int n, int[] primes) {
        TreeSet<Long> set = new TreeSet<>();
        long ans = 1;
        for (int i = 1; i < n; i++) {
            for (int prime : primes) {
                set.add(ans * prime);
            }
            ans = set.pollFirst();
        }
        return Math.toIntExact(ans);
    }
}
